#include <stdio.h>
#include <stdlib.h>
                   
int RandomNumber()
{
    return rand() % 1000;
}


void Sort(unsigned int *massiv,int begin, int end);          //program sorts array from begin to end
void IncertionSort(unsigned int *massiv, int begin, int end, int medium);    

//In main we pass quantity of numbers(which we will sort)                                            
int main(int argc, char *argv[]) {
    if (argc < 2) {
	    printf("Lack of data. Exit.\n");
	    exit(EXIT_FAILURE);
    }
    int size = atoi(argv[1]);
    unsigned int *massiv;

    if (size > 0) {
     	massiv = (unsigned int*)malloc(sizeof(unsigned int) * size);
     	for (int i = 0; i < size; i++) {
             massiv[i] = RandomNumber();
	         printf("%d ", massiv[i]);
	    }
        printf("\n");

     	Sort(massiv, 0, size - 1);

	    for (int i = 0; i < size; i++) {
		    printf("%d ", massiv[i]);
	    }

        free(massiv);   
    }

    printf("\n");
    return 0;
}



void IncertionSort(unsigned int *massiv, int begin, int end, int medium) {
    unsigned int* c;

    if (begin >= end) {
	    return;
	}

    int i_int = begin; 
    int j_int = medium + 1; 
    int step = 0;
    c = (unsigned int*)malloc(sizeof(unsigned int) * (end - begin + 1));

    while (step < (end - begin + 1)) {
        if (massiv[i_int] < massiv[j_int]) {
            c[step] = massiv[i_int];
            i_int++;
            step++;
        } else {
            c[step] = massiv[j_int];
            j_int++;
            step++;
        }
        

        if (i_int > medium && j_int <= end) {
            for (; j_int <= end; j_int++) {
                c[step] = massiv[j_int];
                step++;
            }
        }
        if (i_int <= medium && j_int > end) {
            for (; i_int <= medium; i_int++) {
                c[step] = massiv[i_int];
                step++;
            }
        }

    }

    for (int i = 0; i < (end - begin + 1); i++) massiv[begin + i] = c[i];
    free(c);
}

void Sort(unsigned int *massiv,int begin,int end) {
    int medium;
    if(begin >= end) return;
    medium = end/2 + begin/2;

    Sort(massiv, begin, medium);
    Sort(massiv, medium + 1, end);
    IncertionSort(massiv, begin, end, medium);
 
}

